// 387. 字符串中的第一个唯一字符

function firstUniqChar(s: string): number {
    let count = new Array(26)
    count.fill(0)
    const charCodeOfa = 'a'.charCodeAt(0)
    for(let i=0;i<s.length;i++){
        let c = s.charCodeAt(i)
        count[c-charCodeOfa]++
    }
    for(let i=0;i<s.length;i++){
        let c = s.charCodeAt(i)
        if(count[c-charCodeOfa]==1) return i
    }
    return -1
};


// 240. 搜索二维矩阵 II
function searchMatrix(matrix: number[][], target: number): boolean {
    const mat = matrix
    const row = matrix.length
    if(row==0) return false
    const col = matrix[0].length
    const t = target


    /**
     * 从左下角超上和右看，就是一颗二叉搜索树  O(row+col)
     * @param r 
     * @param c 
     */
    function find(r:number,c:number):boolean{
        if(r>=row||c>=col||r<0||c<0) return false
        const curV = mat[r][c]
        if(curV==t) return true
        if(curV<t) return find(r,c+1)
        else return find(r-1,c)
    }

    return find(row-1,0)
};


// 162. 寻找峰值
function findPeakElement(nums: number[]): number {
    
    // if(nums.length==1) return 0
    // if(nums.length>=2){
    //     if(nums[0]>nums[1]) return 0
    //     else if(nums[nums.length-1]>nums[nums.length-2]) return nums.length-1
    // }

    // for(let i=1;i<nums.length-1;i++){
    //     if(nums[i]>nums[i+1]&&nums[i]>nums[i-1]) return i
    // }
    // return -1


    /*
    奇怪的折半查找
     */

    let l = 0
    let r = nums.length-1
    while(l<r){
        let mid = Math.floor((l+r)/2)
        if(nums[mid]>nums[mid+1]) r= mid
        else l = mid+1
    }
    return l
};

// console.log(findPeakElement([2,3,1]))

// 127. 单词接龙
function ladderLength_(beginWord: string, endWord: string, wordList: string[]): number {
    


    /*
        搜索分两种
        但是向这种各个边权值都相等的应该用bfs找最小值
    */

    //返回两个字符串是否可以直接转换（图是否可达,自己和自己定为不可达）
    function countDiff(s1:string,s2:string):boolean{
        let diff = false
        for(let i=0;i<s1.length;i++){
            if(s1.charAt(i)!=s2.charAt(i)) {
                if(diff) return false
                diff = true
            }
        }
        return diff
    }
    function createGraph(list:string[]):number[][]{
        const len = list.length
        // let graph:number[][] = new Array(len).map(()=>[])
        let graph:number[][] = new Array(len)
        for(let i=0;i<graph.length;i++){
            graph[i] = new Array()
        }
        for(let i=0;i<len;i++){
            for(let j=i+1;j<len;j++){
                if(countDiff(list[i],list[j])) {
                    graph[i].push(j)
                    graph[j].push(i)
                }
                
            }
        }
        return graph
    }

    const graph = createGraph(wordList)
    let ans = 1
    let vis:boolean[] = new Array(wordList.length).fill(false)
    let que:number[] = []

    for(let i=0;i<wordList.length;i++){
        if(countDiff(wordList[i],beginWord)) 
        {
            if(wordList[i]==endWord) return 2
            que.push(i)
        }
    }
    while(que.length!=0){
        let curLen = que.length
        ans++
        for(let i=0;i<curLen;i++){
            let t = que.shift() as number
                vis[t] = true
                for(let to of graph[t]){
                    if(wordList[to]==endWord) {
                        ans++
                        return ans
                    }else if(!vis[to]){
                        que.push(to)
                    }
                }
        }
    }
    return 0
}



// 150. 逆波兰表达式求值
function evalRPN(tokens: string[]): number {

    function isOp(c:string):boolean{
        return c =='+'||c =='-'||c =='*'||c =='/'
    }

    function calc(n1:number,n2:number,c:string):number{
        switch(c){
            case'+':
                return n1 + n2
            case'-':
                return n1 - n2
            case'*':
                return n1 * n2
            case'/':
                const ans = n1 / n2
                return ans>0?Math.floor(ans):Math.ceil(ans)
        }
        return NaN
    }

    let numSta:Array<number> = []
    tokens.forEach(v=>{
        if(isOp(v)){
            let n2:number = numSta.pop() as number
            let n1:number = numSta.pop() as number
            numSta.push(calc(n1,n2,v))
        }else{
            numSta.push(Number.parseInt(v))
        }
    })
    return numSta.pop() as number
};

// 13. 罗马数字转整数
function romanToInt(s: string): number {

    let transition:Map<string,number> = new Map()
    transition.set('I',1)
    transition.set('V',5)
    transition.set('X',10)
    transition.set('L',50)
    transition.set('C',100)
    transition.set('D',500)
    transition.set('M',1000)
    transition.set('',0)

    // const except = ['IV','IX','XL','XC','CD','CM']
    // function parseNum(num:string):number{
    //     if(num.length==1) return transition.get(num) as number
    //     const c1 = num.charAt(0)
    //     const c2 = num.charAt(1)
    //     if(c1=='I'){
    //         if(c2=='V') return 4
    //         else if (c2=='X') return 9
    //     } else if (c1=='X'){
    //         if(c2=='L') return 40
    //         else if (c2=='C') return 90
    //     }else if(c1=='C'){
    //         if(c2=='D') return 400
    //         else if (c2=='M') return 900
    //     }
    //     return 0
    // }
    // let ans = 0
    // let next = ''
    // let cur =''
    // for(let i=0;i<s.length;i++){
    //     next= s.charAt(i+1)||''
    //     cur = s.charAt(i)
    //     if(except.indexOf(cur+next)!=-1){
    //         i++
    //         ans += parseNum(cur+next)
    //     }else{
    //         ans += parseNum(cur)
    //     }
    // }
    // return ans

    /**
        左>=右 正常
        左小于右 左-右
     */
    let ans =0
    for(let i=0;i<s.length;i++){
        let cur = s.charAt(i)
        let next = s.charAt(i+1)||''
        let n1 = transition.get(cur) as number
        let n2 = transition.get(next) as number
        if(n1>=n2) ans+=n1
        else{
            ans+= (n2-n1)
            i++
        }
    }
    return ans

};

// 289. 生命游戏
function gameOfLife(board: number[][]): void {
    enum Status{dead,live,goDead,goLive}
    const posX:number[] = [-1,-1,-1,0,0,1,1,1]
    const posY:number[] = [-1,0,1,-1,1,-1,0,1]
    const row = board.length
    const col = board[0].length
    /**
     * 
     * [0,1,0]
     * [0,0,1]
     * [1,1,1]
     * [0,0,0]
     */
    for(let i=0;i<row;i++){
        for(let j=0;j<col;j++){
            let liveCell = 0
            for(let p=0;p<posX.length;p++){
                const x = i+posX[p]
                const y = j+posY[p]
                if(x>=0&&x<row&&y>=0&&y<col){
                    if(board[x][y]==Status.live||board[x][y]==Status.goDead) liveCell++
                }
            }
            if(board[i][j]==Status.live&&(liveCell<2||liveCell>3)) board[i][j] = Status.goDead
            // else if(board[i][j]==Status.live&&)  
            else if(board[i][j]==Status.dead&&(liveCell==3)) board[i][j] = Status.goLive
        }
    }
    for(let i=0;i<row;i++){
        for(let j=0;j<col;j++){
            if(board[i][j]==Status.goDead) board[i][j] = Status.dead
            else if(board[i][j]==Status.goLive) board[i][j] = Status.live

        }
    }
};


// 5534. 可见点的最大数目  too hard for me
function visiblePoints(points: number[][], angle: number, location: number[]): number {
    let ans =0
    let angleSet:number[] = []
    const X = location[0]
    const Y = location[1]
    points.forEach((v)=>{
        let x = v[0]
        let y = v[1]
        if(x==X&&y==Y) ans++
        else angleSet.push(Math.atan2(x-X,y-Y)*180/Math.PI)
    })
    angleSet.sort((a,b)=>a-b)
    //要围成一个圈
    let size = angleSet.length
    for(let i=0;i<size;i++){
        angleSet.push(360+angleSet[i])
    }
    //滑动窗口
    let p = 0
    let l = 0
    let r = 0
    let winMax = 0
    const EPSILON = 1e-6
    while(r<angleSet.length){
        //把元素加入窗口
        winMax = angleSet[r]
        // 指针右移
        r++
        // 向右移动l收缩窗口
        while(winMax-angleSet[l]-angle>EPSILON){
            l++
        }
        //获取窗口的大小
        p = Math.max(p,r-l)
    }  
    return ans+p 
};

// 15. 三数之和
function threeSum(nums: number[]): number[][] {
    let ans:number[][] = []
    const len = nums.length
    nums.sort((a,b)=>a-b)
    for(let i=0;i<len;i++){
        //去重
        if(i>0&&nums[i]==nums[i-1]) continue 
        //!双指针
        let mid = i+1
        let last = len-1
        while(mid<last){
            //去重复
            while(mid>i+1&&mid<last&&nums[mid]==nums[mid-1]) mid++
            while(last>mid&&last!=len-1&&nums[last]==nums[last+1]) last--
            if(mid>=last) break
            let sum = nums[mid]+nums[last]+nums[i]
            if(sum==0){
                ans.push([nums[i],nums[mid],nums[last]])
                mid++
            }else if(sum>0){
                last--
            }else{
                mid++
            }
        }
    }
    return ans
};

// 18. 四数之和
function fourSum(nums: number[], target: number): number[][] {
    let ans:number[][] = []
    nums.sort((a,b)=>a-b)
    let len = nums.length
    for(let i=0;i<len-3;i++){
        if(i>0&&nums[i]==nums[i-1])continue
        for(let j=i+1;j<len-2;j++){
            if(j>i+1&&nums[j]==nums[j-1])continue
                let mid = j+1
                let last = len-1
                let sum = nums[i]+nums[j]
                while(mid<last){
                    while(mid<last&&mid>j+1&&nums[mid]==nums[mid-1]) mid++
                    while(mid<last&&last!=len-1&&nums[last]==nums[last+1]) last--
                    if(mid>=last) break
                    let tmp = sum+nums[mid]+nums[last]
                    if(tmp==target){
                        ans.push([nums[i],nums[j],nums[mid],nums[last]])
                        mid++
                    }else if(tmp>target){
                        last--
                    }else{
                        mid++
                    }
                }
        }
    }
    return ans
};

// 90. 子集 II
function subsetsWithDup(nums: number[]): number[][] {
    
    nums.sort((a,b)=>a-b)
    let ans:number[][] = []
    let vis:boolean[] = new Array(nums.length).fill(false)
    function dfs(vis:boolean[],tmp:number[],start:number):void{
        if(start>=nums.length) {
            ans.push(JSON.parse(JSON.stringify(tmp)))
            return
        }
        //加入这个
        if(!(start>0&&nums[start]==nums[start-1]&&vis[start-1]==false)){
            vis[start] = true
            tmp.push(nums[start])
            dfs(vis,tmp,start+1)
            vis[start] = false
            tmp.pop()
        }
        //不加入这个
        dfs(vis,tmp,start+1)
    }
    dfs(vis,[],0)
    return ans
};

// ! 334. 递增的三元子序列  TOO HARD
function increasingTriplet(nums: number[]): boolean {
    let l1 = Number.MAX_VALUE
    let l2 = Number.MAX_VALUE
    for(let n of nums){
        if(l1>=n) l1=n
        else if(l2>=n) l2=n
        else return true
    }
    return false
};

// 49. 字母异位词分组
function groupAnagrams(strs: string[]): string[][] {
    let map:Map<string,string[]> = new Map()
    const base = 2333
    const mod = 1e7+357
    function hash(str:string):string{
        // let ans = 0
        // for(let i=0;i<str.length;i++){
        //     const c = str.charCodeAt(i)
        //     ans=(ans+base*(Math.pow(c-77,3)))%mod
        // }
        // return ans
        let set:string[] = []
        for(let i=0;i<str.length;i++){
            set.push(str.charAt(i))
        }
        set.sort((a,b)=>a.charCodeAt(0)-b.charCodeAt(0))
        return set.reduce((pre,cur)=>pre+cur,'')
    }
    for(let str of strs){
        let code = str==''?'':hash(str)
        if(!map.has(code)){
            map.set(code,[str])
        }else{
            let tmp = map.get(code)as string[]
            tmp.push(str)
            map.set(code,tmp)
        }
    }
    let ans:string[][] = []
    for(let kv of map){
        ans.push(kv[1])
    }
    return ans
};

// 75. 颜色分类
function sortColors(nums: number[]): void {
    enum Color{
        RED,WHITE,BLUE
    }
    let pRed = 0
    let pBlue = nums.length-1
    let mid = 0
    while(mid<=pBlue){
        switch(nums[mid]){
            case Color.RED:
                [nums[mid],nums[pRed]] = [nums[pRed],nums[mid]]
                pRed++
                mid++   //交换过来的肯定是白色,所以可以直接mid++了,同时也保证了pRed不会比mid大
                break
            case Color.BLUE:
                [nums[mid],nums[pBlue]] = [nums[pBlue],nums[mid]]
                pBlue--
                break
            default:
                mid++
        }
    }
};

// 89. 格雷编码  ...
function grayCode(n: number): number[] {
    if(n==0) return [0]
    n--
    const a = grayCode(n)
    const left = a.map(v=>v)
    const right = a.reverse().map(v=>(1<<n)|v)
    return left.concat(right)
};
// 54. 螺旋矩阵
function spiralOrder(matrix: number[][]): number[] {
    //!转圈遍历
    function loop(matrix:number[][],start:number,rows:number,cols:number):number[]{
        let res:number[] = []
        //右上
        const rt = cols - start -1
        // 右下
        const rb = rows - start -1 
        //向右
        for(let i=start;i<=rt;i++) res.push(matrix[start][i])
        //向下
        for(let i=start+1;i<=rb;i++) res.push(matrix[i][rt])
        //向左
        if(rb!=start){
            for(let i=rt-1;i>=start;i--) res.push(matrix[rb][i])
        }
        //向上
        if(rt!=start){
            for(let i=rb-1;i>start;i--) res.push(matrix[i][start])
        }
        return res
    }

    let ans:number[] = []
    if(matrix.length!=0&&matrix[0].length!=0){
        const rows = matrix.length
        const cols = matrix[0].length
        let start= 0
        while(start*2<rows&&start*2<cols){
            ans.push(...loop(matrix,start,rows,cols))
            start++
        }
    }
    return ans
};

